# !/usr/bin/env python
# -*-coding:utf-8 -*-
"""
@Author : Ayao
@Time   : 2022/5/21
@File   : 对角线遍历.py
"""

# https://leetcode.cn/leetbook/read/array-and-string/cuxq3/
#  参考题解：https://leetcode.cn/problems/diagonal-traverse/solution/dui-jiao-xian-bian-li-bian-jie-tiao-jian-4qlc/
"""
有两个特点:
1、第一个是对角线上的数据（x,y）对应 x+y 的值都是一致的。
2、当 x+y 为奇数时对角线上的数据正序输出，为偶数时倒叙输出。
"""

from typing import List


class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        n = len(mat)
        m = len(mat[0])
        flag = 0
        ans = []

        for z in range(0, m + n - 1):
            if flag:
                for i in range(max(0, z - m + 1), min(z, n - 1) + 1):
                    ans.append(mat[i][z - i])
                flag = 0
            else:
                for i in range(min(z, n - 1), max(0, z - m + 1) - 1, -1):
                    ans.append(mat[i][z - i])
                flag = 1

        return ans


if __name__ == '__main__':
    mat = [[1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12]]
    Solution().findDiagonalOrder(mat)
